
#二叉树节点类
class Node():
    def __init__(self,value,left,right):
        self.value = value
        self.left = left
        self.right = right

#建立一个二叉树
a7 = Node(70,None,None)
a6 = Node(60,None,None)
a5 = Node(50,None,None)
a4 = Node(40,a6,a7)
a3 = Node(30,a4,a5)
a2 = Node(20,None,None)
a1 = Node(10,a2,a3)

# print(a1.value)
# print(a1.left.value)
# print(a1.right.value)

def dfsRec(root):
    '''使用递归遍历二叉树'''
    if root==None:
        return
    print(root.value)   #这里打印是中序排列
    dfsRec(root.left)
    # print(root.value)   #这里打印是前序排列
    dfsRec(root.right)
    # print(root.value)   #这里打印是后序排列

#dfsRec(a1)  #递归遍历二叉树


def dfsStack(root):
    '''使用栈实现遍历二叉树'''
    a = []  # python 的list有 pop()函数, 相当于栈的出栈
    a.append(root)
    while a != []:
        now = a.pop()
        print(now.value)    #父节点优先输出, 然后输出左右节点
        if now.right != None:
            a.append(now.right)
        if now.left != None:
            a.append(now.left)

#dfsStack(a1)    #栈遍历二叉树


class TreeNode():
    '''普通树的节点, 允许有多个节点'''
    def __init__(self,value,*son_list):
        self.value = value  #当前值
        self.son = []
        # print(son_list)
        for i in son_list:
            self.son.append(i)       #儿子列表

def DFSTreeStack(root):
    '''使用栈深度优先遍历树'''
    a = []
    a.append(root)
    while a!= []:
        now = a.pop()
        print(now.value)
        for i in range(len(now.son)-1,-1,-1):
            if now.son[i] != None:
                a.append(now.son[i])

from queue import Queue
def DFSTreeQueue(root):
    '''使用队列广度优先遍历树'''
    q = Queue(1000)
    q.put(root)
    while q.empty()!=True:
        now = q.get()
        print(now.value)
        for i in now.son:
            if i!=None:
                q.put(i)




t10 = TreeNode(10)
t9 = TreeNode(9)
t8 = TreeNode(8)
t7 = TreeNode(7)
t6 = TreeNode(6,t10)
t5 = TreeNode(5,t9)
t4 = TreeNode(4,t8)
t3 = TreeNode(3,t6,t7)
t2 = TreeNode(2,t5)
t1 = TreeNode(1,t2,t3,t4)


# DFSTreeStack(t1)    #栈深度搜索

DFSTreeQueue(t1)    #堆深度搜索








